package com.cn.codebrush.二分查找;

public class No1574删除最短的子数组使剩余数组有序 {
    public static void main(String[] args) {
        int[] nums= {1,2,3,10,4,2,3,5};
        int[] nums1= {5,4,3,2,1};
        int[] nums2={1,2,3};
        int[] nums3={1};
        int[] nums4={1,2,2,3,3,78,5,2,3,2,4,7};

        System.out.println(findLengthOfShortestSubarray(nums));
    }

    /**
     * 左边有序 i  右边有序 j
     * i>j  已经有序
     * 从左边第一个开始比较右边区间每一个，找出 中间可以截断最小的数组
     * * * 查找可以采用二分查找
     * @param arr
     * @return
     */
    public static int findLengthOfShortestSubarray(int[] arr) {
        int n = arr.length;
        int i = 1; int j = n-1;
        while(i<n && arr[i]>=arr[i-1]){i++;}
        while(j>=1 && arr[j]>=arr[j-1]){j--;}
        if(i>j){return 0;}

        int res = j;
        for(int k=0;k<i;k++){
            int target = arr[k];
            int l=j-1,r=n; //扫描右边区间
            while(l+1<r){   //判断右边区间是否都大于 target  1. 二分查找  2. 进行扫描（暴力）
                int mid = (l+r)>>1;
                if(arr[mid] < target){
                    l=mid;
                } else {
                    r=mid;
                }
            }
            res=Math.min(res,r-k-1);

        }
        return res;
    }
}
